def main():
MOD = int(1e9 + 7)
dp = [0] * 200005
dp[0] = 1
for i in range(1, 200005):
dp[i] += dp[i - 1]
if i - 2 >= 0:
dp[i] += dp[i - 2] dp[i] %= MOD
dps = dp.copy() for i in range(1, 200005):
dps[i] += dps[i - 1]
dps[i] %= MOD
n, p = readIntArr()
a = readIntArr()
a.sort()
allNums = set(a)
vi = [False] * n
for i, x in enumerate(a):
while x > 0 and (x % 2 == 1 or x % 4 == 0):
if x % 2 == 1: x //= 2
elif x % 4 == 0: x //= 4
if x in allNums: vi[i] = True
break
ans = 0
for i, x in enumerate(a):
if not vi[i]:
extraLength = p - x.bit_length()
if extraLength >= 0:
ans += dps[extraLength]
ans %= MOD
print(ans)
return
import sys
input=sys.stdin.buffer.readline
def oneLineArrayPrint(arr):
print(' '.join([str(x) for x in arr]))
def multiLineArrayPrint(arr):
print('\n'.join([str(x) for x in arr]))
def multiLineArrayOfArraysPrint(arr):
print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))
def readIntArr():
return [int(x) for x in input().split()]
def makeArr(defaultValFactory,dimensionArr): dv=defaultValFactory;da=dimensionArr
if len(da)==1:return [dv() for _ in range(da[0])]
else:return [makeArr(dv,da[1:]) for _ in range(da[0])]
def queryInteractive(a, b, c):
print('? {} {} {}'.format(a, b, c))
sys.stdout.flush()
return int(input())
def answerInteractive(x1, x2):
print('! {} {}'.format(x1, x2))
sys.stdout.flush()
inf=float('inf')
from math import gcd,floor,ceil
import math
for _abc in range(1):
main()#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long int
#define pb push_back
#define f(i, j, k) for (int i = j; i < k; i++)
#define rev(i, j, k) for (int i = j; i >= k; i--)
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define SET(x) cout << fixed << setprecision(x);
const int MOD = 1e9+7;
int ceil_div(int a, int b) { return (a + b - 1) / b; }
typedef vector<int> vi;
typedef vector<pair<int, int>> vp;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> pbds; // find_by_order, order_of_key
void solve()
{
int n,p;
cin>>n>>p;
vi a(n);
f(i,0,n)
{
cin>>a[i];
}
sort(all(a));
map<int,int>mp;
vi dp(p,0);
f(i,0,n)
{
int temp=a[i];
int f=0;
while(temp>0 && (temp%2==1 || temp%4==0))
{
if(temp%4==0)
{
temp/=4;
}
else if(temp%2==1)
{
temp/=2;
}
else
{
break;
}
if(mp[temp]==1)
{
f=1;
break;
}
}
if(f==0)
{
mp[a[i]]+=1;
int x=log2(a[i]);
if(x<p)
dp[x]+=1;
}
}
int ans=0;
f(i,0,p)
{
if(i>=1)
{
dp[i]+=dp[i-1];
dp[i]%=MOD;
}
if(i>=2)
{
dp[i]+=dp[i-2];
dp[i]%=MOD;
}
ans+=dp[i];
ans%=MOD;
}
cout<<ans<<"\n";
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tt = 1;
// cin >> tt;
f(i, 1, tt + 1)
{
solve();
}
return 0;
}1584B - Coloring Rectangles | 1562B - Scenes From a Memory |
1521A - Nastia and Nearly Good Numbers | 208. Implement Trie |
1605B - Reverse Sort | 1607C - Minimum Extraction |
1604B - XOR Specia-LIS-t | 1606B - Update Files |
1598B - Groups | 1602B - Divine Array |
1594B - Special Numbers | 1614A - Divan and a Store |
2085. Count Common Words With One Occurrence | 2089. Find Target Indices After Sorting Array |
2090. K Radius Subarray Averages | 2091. Removing Minimum and Maximum From Array |
6. Zigzag Conversion | 1612B - Special Permutation |
1481. Least Number of Unique Integers after K Removals | 1035. Uncrossed Lines |
328. Odd Even Linked List | 1219. Path with Maximum Gold |
1268. Search Suggestions System | 841. Keys and Rooms |
152. Maximum Product Subarray | 337. House Robber III |
869. Reordered Power of 2 | 1593C - Save More Mice |
1217. Minimum Cost to Move Chips to The Same Position | 347. Top K Frequent Elements |